Practice | GeeksforGeeks | A computer science portal for geeks
▲
LIVE   BATCHES
 Back To Course
Quiz

This track of the course covers the topic "Greedy Algorithms".

In details, this track will cover:

  • Basics: Introduction to greedy algorithms.

Objective: The objective of this track is to familiarize learners with Greedy Algorithms.

Track Content:

  • 1 Video Lecture on Greedy Algorithms.
  • Theoretical Articles.
  • Programming practice problems.
  • 10 Quiz questions for practice.

Assessment: All Tracks in every week are associated with weekly contests.

We have combined Classroom and Theory tab and created a new Learn tab for easy access. You can access Classroom and Theory from the left panel.
Classroom Theory

  Introduction to Greedy Algorithms 


This video introduces us to the Greedy Algorithms and its various Applications.
Codes:

  Activity Selection Problem 


This video discusses the Activity Selection Problem.

  Activity Selection Solution in C++ 


This video talks about C++ Solution of Activity Selection Problem.
Codes:

  Activity Selection Solution in Java 


This video talks about Java Solution of Activity Selection Problem.
Codes:

  Fractional Knapsack 


 This video discusses the Fractional Knapsack Problem.

  Fractional Knapsack in C++ 


This video talks about C++ implementation of Fractional Knapsack problem.
Codes:

  Fractional Knapsack in Java 


This video talks about Java implementation of the Greedy Algorithm for Fraction Knapsack problem
Codes:

  Job Sequencing Problem 


This video discusses the working and the concept behind the famous Job Sequencing Problem

  Introduction to Greedy Algorithms 

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to the global optimal solution are best fit for Greedy.

For example, consider the Fractional Knapsack Problem. The problem states that:
Given a list of elements with specific values and weights associated with them, the task is to fill a Knapsack of weight W using these elements such that the value of knapsack is maximum possible.

Note: You are allowed to take a fraction of an element also in order to maximize the value.

The local optimal strategy is to choose the item that has maximum value vs weight ratio. This strategy also leads to global optimal solution because we are allowed to take fractions of an item.



In general, the Greedy Algorithm can be applied to solve a problem if it satisfies the below property:

At every step, we can make a choice that looks best at the moment, and we get the optimal solution of the complete problem.


Let us consider one more problem known as the Activity Selection Problem to understand the use of Greedy Algorithms.

Problem: You are given N activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.
Example 1: Consider the following 3 activities sorted by
finish time.
     start[]  =  {10, 12, 20};
     finish[] =  {20, 25, 30};
A person can perform at most two activities. The 
maximum set of activities that can be executed 
is {0, 2} [ These are indexes in start[] and 
finish[] ]

Example 2: Consider the following 6 activities 
sorted by finish time.
     start[]  =  {1, 3, 0, 5, 8, 5};
     finish[] =  {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The 
maximum set of activities that can be executed 
is {0, 1, 3, 4} [ These are indexes in start[] and 
finish[] ]

The greedy choice is to always pick the next activity whose finish time is least among the remaining activities and the start time is more than or equal to the finish time of previously selected activity. We can sort the activities according to their finishing time so that we always consider the next activity as minimum finishing time activity.

To do this:
  1. Sort the activities according to their finishing time.
  2. Select the first activity from the sorted array and print it.
  3. Do following for remaining activities in the sorted array.
    • If the start time of this activity is greater than or equal to the finish time of previously selected activity then select this activity and print it.

  Job Sequencing Problem | Greedy Approach 

Problem: Given an array of jobs where every job has a deadline and associated profit if the job is finished before the deadline. It is also given that every job takes a single unit of time, so the minimum possible deadline for any job is 1. How to maximize total profit if only one job can be scheduled at a time.

Examples: 
Input: Four Jobs with following deadlines and profits
  JobID    Deadline      Profit
    a        4            20   
    b        1            10
    c        1            40  
    d        1            30
Output: Following is maximum profit sequence of jobs
        c, a   

Input: Five Jobs with following deadlines and profits
   JobID     Deadline     Profit
     a         2           100
     b         1           19
     c         2           27
     d         1           25
     e         3           15
Output: Following is maximum profit sequence of jobs
        c, a, e


This is a standard Greedy Algorithm problem. Following is the greedy algorithm to solve the above problem:
1) Sort all jobs in decreasing order of profit.
2) Initialize the result sequence as the first job in sorted jobs.
3) Do following for remaining n-1 jobs
.......a) If the current job can fit in the current result sequence 
          without missing the deadline, add the current job to the result.
          Else ignore the current job.

Implementation:
// C++ program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
#include<iostream>
#include<algorithm>
using namespace std;
// A structure to represent a job
struct Job
{
char id; // Job Id
int dead; // Deadline of job
// Profit if job is over
// before or on deadline
int profit;
};
// This function is used for sorting all
// jobs according to profit
bool comparison(Job a, Job b)
{
return (a.profit > b.profit);
}
// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n)
{
// Sort all jobs according to
// decreasing order of prfit
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// Java program to find the maximum profit
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.Arrays;
// A class to represent a job
class Job implements Comparable<Job>
{
char id; // Job Id
int dead; // Deadline of job
// Profit if job is over
// before or on deadline
int profit;
Job(char id, int dead, int profit) {
this.id = id;
this.dead = dead;
this.profit = profit;
}
// This function is used for sorting all
// jobs according to decreasing order of profit
@Override
public int compareTo(Job o) {
if(this.profit < o.profit)
return 1;
return -1;
}
};
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Complete Code/Output: 
// C++ program to find the maximum profit 
// job sequence from a given array
// of jobs with deadlines and profits
#include<iostream>
#include<algorithm>
using namespace std;

// A structure to represent a job
struct Job
{
    char id; // Job Id
    int dead; // Deadline of job
    
    // Profit if job is over 
    // before or on deadline
    int profit; 
};

// This function is used for sorting all
// jobs according to profit
bool comparison(Job a, Job b)
{
    return (a.profit > b.profit);
}

// Returns minimum number of platforms reqquired
void printJobScheduling(Job arr[], int n)
{
    // Sort all jobs according to 
    // decreasing order of prfit
    sort(arr, arr+n, comparison);

    int result[n]; // To store result (Sequence of jobs)
    bool slot[n]; // To keep track of free time slots

    // Initialize all slots to be free
    for (int i=0; i<n; i++)
        slot[i] = false;

    // Iterate through all given jobs
    for (int i=0; i<n; i++)
    {
        // Find a free slot for this job 
        // (Note that we start
        // from the last possible slot)
        for (int j=min(n, arr[i].dead)-1; j>=0; j--)
        {
            // Free slot found
            if (slot[j]==false)
            {
                result[j] = i; // Add this job to result
                slot[j] = true; // Make this slot occupied
                break;
            }
        }
    }

    // Print the result
    for (int i=0; i<n; i++)
    if (slot[i])
        cout << arr[result[i]].id << " ";
}

// Driver Code
int main()
{
    Job arr[] = { {'a', 2, 100}, {'b', 1, 19}, {'c', 2, 27},
                {'d', 1, 25}, {'e', 3, 15}};
                
    int n = sizeof(arr)/sizeof(arr[0]);
    
    cout << "Following is maximum profit sequence of job : ";
    
    printJobScheduling(arr, n);
    
    return 0;
}
// Java program to find the maximum profit 
// job sequence from a given array
// of jobs with deadlines and profits
import java.util.Arrays;

// A class to represent a job
class Job implements Comparable<Job>
{
    char id; // Job Id
    int dead; // Deadline of job
    
    // Profit if job is over 
    // before or on deadline
    int profit; 

    Job(char id, int dead, int profit) {
        this.id = id;
        this.dead = dead;
        this.profit = profit;
    }
    // This function is used for sorting all
    // jobs according to decreasing order of profit
    @Override
    public int compareTo(Job o) {
        if(this.profit < o.profit)
            return 1;
        return -1;
    }
};

class GFG
{
    // Returns minimum number of platforms reqquired
    static void printJobScheduling(Job arr[], int n)
    {
        // Sort all jobs according to 
        // decreasing order of prfit
        Arrays.sort(arr);
        
        // To store result (Sequence of jobs)
        int result[] = new int[n]; 
        // To keep track of free time slots
        boolean slot[] = new boolean[n];

        // Initialize all slots to be free
        for (int i=0; i<n; i++)
                slot[i] = false;

        // Iterate through all given jobs
        for (int i=0; i<n; i++)
        {
            // Find a free slot for this job 
            // (Note that we start
            // from the last possible slot)
            for (int j=Math.min(n, arr[i].dead)-1; j>=0; j--)
            {
                // Free slot found
                if (slot[j]==false)
                {
                    result[j] = i; // Add this job to result
                    slot[j] = true; // Make this slot occupied
                    break;
                }
            }
        }

        // Print the result
        for (int i=0; i<n; i++)
            if (slot[i])
                System.out.print(arr[result[i]].id + " ");
    }

    // Driver Code
    public static void main(String args[])
    {
        Job arr[] = {new Job('a', 2, 100), 
                     new Job('b', 1, 19), 
                     new Job('c', 2, 27), 
                     new Job('d', 1, 25), 
                     new Job('e', 3, 15)};
                     
        int n = arr.length;

        System.out.print("Following is maximum profit"
                                +" sequence of job : ");

        printJobScheduling(arr, n);
    }
}
Following is maximum profit sequence of job : c a e

Time Complexity of the above solution is O(n2). It can be optimized using Disjoint Set Data Structure. Please refer below post for details.
Activity Selection

Asked In: Facebook Morgan Stanley

Submissions: 7614   Accuracy:

37.38%

  Difficulty: Easy   Marks: 2
Huffman Decoding
Submissions: 3767   Accuracy:

64.45%

  Difficulty: Easy   Marks: 2
N meetings in one room

Asked In: Amazon Flipkart MakeMyTrip Microsoft

Submissions: 12326   Accuracy:

43.1%

  Difficulty: Easy   Marks: 2
Fractional Knapsack

Asked In: Microsoft

Submissions: 12942   Accuracy:

45.14%

  Difficulty: Medium   Marks: 4
Largest number with given sum

Asked In: Microsoft

Submissions: 5678   Accuracy:

54.02%

  Difficulty: Easy   Marks: 2
Job Sequencing Problem

Asked In: Accolite Microsoft

Submissions: 10727   Accuracy:

48.94%

  Difficulty: Medium   Marks: 4
Question 1 [1 Marks]
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge weighted directed graph with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? (GATE CS 2004)

gate2004
A
P, Q, R, S, T, U
B
P, Q, R, U, S, T
C
P, Q, R, U, T, S
D
P, Q, T, R, U, S
Explanation

DSASP-W9 LIVE

Greedy

Contest Max Score: 250

Duration: 2 Hrs 0 Mins

If you are facing any issue on this page. Please let us know.